#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    bool canPartitionGrid(vector<vector<int>> &grid)
    {
        vector<long> sum(grid[0].size(), 0);
        vector<long> sum_prefix(grid[0].size(), 0);
        vector<long> sum_suffix(grid[0].size(), 0);
        for (int i = 0; i < grid[0].size(); i++)
        {
            for (int k = 0; k < grid.size(); k++)
                sum[i] += grid[k][i];
        }
        sum_prefix[0] = sum[0];
        for (int i = 1; i < grid[0].size(); i++)
            sum_prefix[i] = sum[i] + sum_prefix[i - 1];
        sum_suffix[grid[0].size() - 1] = sum[grid[0].size() - 1];
        for (int i = grid[0].size() - 2; i >= 0; i--)
            sum_suffix[i] = sum[i] + sum_suffix[i + 1];
        for (int i = 0; i < grid[0].size() - 1; i++)
            if (sum_prefix[i] == sum_suffix[i + 1])
                return true;

        sum = vector<long>(grid.size(), 0);
        sum_prefix = vector<long>(grid.size(), 0);
        sum_suffix = vector<long>(grid.size(), 0);
        for (int i = 0; i < grid.size(); i++)
        {
            for (int k = 0; k < grid[0].size(); k++)
                sum[i] += grid[i][k];
        }
        sum_prefix[0] = sum[0];
        for (int i = 1; i < grid.size(); i++)
            sum_prefix[i] = sum[i] + sum_prefix[i - 1];
        sum_suffix[grid.size() - 1] = sum[grid.size() - 1];
        for (int i = grid.size() - 2; i >= 0; i--)
            sum_suffix[i] = sum[i] + sum_suffix[i + 1];
        for (int i = 0; i < grid.size() - 1; i++)
            if (sum_prefix[i] == sum_suffix[i + 1])
                return true;

        return false;
    }
};
int main()
{
    cout << "Code3546" << endl;
    Solution s;
    vector<vector<int>> grid = {{1, 4}, {2, 3}};
    cout << s.canPartitionGrid(grid) << endl;
    return 0;
}